/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package hoja3;

import java.util.*;

/**
 *
 * @author asus
 */
public class Hoja3 {
     
    /**
     * Método que implementa el algoritmo de selectionsort
     * @param data
     * @param n
     * @return 
     */
    public static int[] selectionSort(int data[], int n) {
        int numUnsorted = n;
        int index;
        int max;
        while (numUnsorted > 0) {
            max = 0;
            for (index = 1; index < numUnsorted; index++) {
                if (data[max] < data[index]) max = index;
            }
            swap(data, max, numUnsorted-1);
            numUnsorted--;
        }
        return data;
    }
    
    /**
     * Método separado para medir el tiempo de corrida para selectionsort con un arreglo ordenado
     * @param data
     * @param n
     * @return 
     */
    public static int[] selectionSortO(int data[], int n) {
        int numUnsorted = n;
        int index;
        int max;
        while (numUnsorted > 0) {
            max = 0;
            for (index = 1; index < numUnsorted; index++) {
                if (data[max] < data[index]) max = index;
            }
            swap(data, max, numUnsorted-1);
            numUnsorted--;
        }
        return data;
    }
    
    /**
     * Método que implementa el algoritmo quicksort, y es llamado para medir su tiempo de ejecución en el profiler
     * @param data
     * @param n
     * @return 
     */
    public static int[] quickSort(int data[], int n) {
        quickSortRecursive(data,0,n-1);
        return data;
    }
    
    /**
     * Método separado para medir el tiempo de corrida para quicksort con un arreglo ordenado
     * @param data
     * @param n
     * @return 
     */
    public static int[] quickSortO(int data[], int n) {
        quickSortRecursive(data,0,n-1);
        return data;
    }
    
    /**
     * Método que realiza la partición de un arreglo para la implementación de quicksort
     * @param data
     * @param left
     * @param right
     * @return 
     */
    private static int partition(int data[], int left, int right) {
        while (true) {
            while (left < right && data[left] < data[right]) right--;
            if (left < right) swap(data,left++,right);
            else return left;

            while (left < right && data[left] < data[right]) left++;
            if (left < right) swap(data,left,right--);
            else return right;
        }
    }
    

    /**
     * Método recursivo que implementa el algoritmo de quicksort
     * @param data
     * @param left
     * @param right 
     */
    private static void quickSortRecursive(int data[],int left,int right) {
        int pivot; // the final location of the leftmost value
        if (left >= right) return;
        pivot = partition(data,left,right); /* 1 - place pivot */
        quickSortRecursive(data,left,pivot-1); /* 2 - sort small */
        quickSortRecursive(data,pivot+1,right);/* 3 - sort large */
    }
    
    /**
     * Intercambia los datos entre dos índices del arreglo suministrado como parámetro
     * @param data
     * @param i
     * @param j 
     */
    private static void swap(int[] data, int i, int j) {
        int temp;
        temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Random gen = new Random();
        
        // La variable n permite controlar el número de datos a ordenar con un sólo cambio de valor
        int n = 2000;
        
        // Crea los arreglos de enteros aleatorios
        int data[] = new int[n];
        for (int i = 0; i < n; i++) {
             data[i] = gen.nextInt();
        }
        int data2[] = data;
        
        // Llama a los métodos para que su desempeño pueda ser medido por el profiler
        int ordenado[] = quickSort(data, n);
        int ordenado2[] = selectionSort(data2, n);
        selectionSortO(ordenado, n);
        quickSortO(ordenado2, n);
    }
        
 }    
    
        


    

